/* WUGraph.java */

package graph;

import dict.*;
import list.*;

/**
 * The WUGraph class represents a weighted, undirected graph.  Self-edges are
 * permitted.
 */

public class WUGraph {
	int vertexTotal;
	int edgeTotal;
	HashTableChained vertexHash;
	HashTableChained edgeHash;
	DList vertexList;
	
	/**
	 * WUGraph() constructs a graph having no vertices or edges.
	 *
	 * Running time:  O(1).
	 */
	public WUGraph() {
		vertexHash = new HashTableChained(10);
		edgeHash = new HashTableChained(10);	
		vertexList = new DList();
	}

	/**
	 * vertexCount() returns the number of vertices in the graph.
	 *
	 * Running time:  O(1).
	 */
	public int vertexCount() {
		return vertexTotal;
	}

	/**
	 * edgeCount() returns the number of edges in the graph.
	 * @return the number of edges in the graph
	 * 
	 * Running time:  O(1).
	 */
	public int edgeCount() {
		return edgeTotal;
	}


	/**
	 * getVertices() returns an array containing all the objects that serve
	 * as vertices of the graph.  The array's length is exactly equal to the
	 * number of vertices.  If the graph has no vertices, the array has length
	 * zero.
	 *
	 * (NOTE:  Do not return any internal data structure you use to represent
	 * vertices!  Return only the same objects that were provided by the
	 * calling application in calls to addVertex().)
	 * 
	 * @return an array containing all the objects that serve as vertices of 
	 * the graph
	 *
	 * Running time:  O(|V|).
	 */
	public Object[] getVertices() {
		Object[] vArray = new Object[vertexTotal];
		if (vertexTotal == 0) {
			return vArray;
		}

		/*  Try to add all the vertices to the vArray but have to surround it with
		 *  try/catch blocks because item() method can throw an InvalidNodeException.
		 *  However, given that I always check that the node is valid before I execute  
		 *  the while loop, the exception should never be thrown.
		 */
		
		int i = 0;
		DListNode vertexNode= (DListNode) vertexList.front();
		
		try {  
			while (vertexNode.isValidNode()) {
				vArray[i] = ( (Vertex) vertexNode.item()).vertexObject;
				i++;
				vertexNode = (DListNode) vertexNode.next();				
			}
		} catch (InvalidNodeException e) {
			Thread.dumpStack();
		}
		return vArray;
	}

	/**
	 * addVertex() adds a vertex (with no incident edges) to the graph.  The
	 * vertex's "name" is the object provided as the parameter "vertex".
	 * If this object is already a vertex of the graph, the graph is unchanged.
	 * @param vertex is the vertex object to be added
	 *
	 * Running time:  O(1).
	 */
	public void addVertex(Object vertex) {
		/* To add a vertex we need to.
		 * 1) update vertexTotal if the vertex is new (not on the graph already)
		 * 2) Update vertexList
		 * 3) update vertexHash 
		 */
		if (vertexHash.find(vertex) != null) {
			return;
		}
		Vertex newVertex = new Vertex(vertex);	
		vertexTotal++;	
		vertexList.insertBack(newVertex);
		newVertex.myNode = (DListNode) vertexList.back();	
		vertexHash.insert(vertex,newVertex);
	}

	/**
	 * removeVertex() removes a vertex from the graph.  All edges incident on the
	 * deleted vertex are removed as well.  If the parameter "vertex" does not
	 * represent a vertex of the graph, the graph is unchanged.
	 * @vertex vertex is the vertex to be removed from the graph
	 *
	 * Running time:  O(d), where d is the degree of "vertex".
	 */
	public void removeVertex(Object vertex) {		
		Vertex v = getVertex(vertex);
		// Case 1: there is no internal vertex that has the vertexObject field 
		// == to parameter vertex.	
		if (v == null) {
			return;
		}
		
		// Case 2: vertex exists and we must walk through its edgeList field to 
		// remove all edges that are in this DList (stored as an item() in each 
		// of the DListNodes).
		// removeEdge should properly update the degree of the vertices and edgeTotal.
		// 
		// NEED TO UPDATE:  vertexTotal, vertexHash, vertexList
		
		Edge e;
		Object o1,o2;
		DListNode edgeNode = (DListNode) v.edgeList.front();
		
		try {
			while (edgeNode.isValidNode()) {
				e = (Edge) edgeNode.item();
				o1 = e.vertexEnds.object1;
				o2 = e.vertexEnds.object2;
				edgeNode = (DListNode) edgeNode.next();
				removeEdge(o1,o2);
			}			
			vertexTotal--;			
			vertexHash.remove(vertex);			
			v.myNode.remove();
		} catch (InvalidNodeException error) {
			Thread.dumpStack();
		}
	}

	/**
	 * isVertex() returns true if the parameter "vertex" represents a vertex of
	 * the graph.
	 * @param vertex is the vertex we want to inspect to see if it is in the graph
	 * @return true if "vertex" represents a vertex of the graph, false otherwise
	 *
	 * Running time:  O(1).
	 */
	public boolean isVertex(Object vertex) {
		if (vertexHash.find(vertex) == null) {
			return false;
		}
		return true;
	}

	/**
	 * degree() returns the degree of a vertex.  Self-edges add only one to the
	 * degree of a vertex.  If the parameter "vertex" doesn't represent a vertex
	 * of the graph, zero is returned.
	 * @param vertex is the vertex we wish to find the degree of
	 * @return degree of "vertex"
	 *
	 * Running time:  O(1).
	 */
	public int degree(Object vertex) {
		Vertex v = getVertex(vertex);
		if (v == null) {
			return 0;
		}	
		return v.degree;
	}
	

	/**
	 * getNeighbors() returns a new Neighbors object referencing two arrays.  The
	 * Neighbors.neighborList array contains each object that is connected to the
	 * input object by an edge.  The Neighbors.weightList array contains the
	 * weights of the corresponding edges.  The length of both arrays is equal to
	 * the number of edges incident on the input vertex.  If the vertex has
	 * degree zero, or if the parameter "vertex" does not represent a vertex of
	 * the graph, null is returned (instead of a Neighbors object).
	 *
	 * The returned Neighbors object, and the two arrays, are both newly created.
	 * No previously existing Neighbors object or array is changed.
	 *
	 * (NOTE:  In the neighborList array, do not return any internal data
	 * structure you use to represent vertices!  Return only the same objects
	 * that were provided by the calling application in calls to addVertex().)
	 * 
	 * @param vertex is the vertex we wish to find the neighbors of
	 * @return a Neighbors object containing a list of neighbors and the associated 
	 * weights for the connecting edges
	 *
	 * Running time:  O(d), where d is the degree of "vertex".
	 */
	public Neighbors getNeighbors(Object vertex) {
	
		Vertex v = getVertex(vertex); // is the INTERNAL representation of the vertex
		if (v == null || v.degree == 0) {
			return null;
		}
		Neighbors n = new Neighbors();		
		n.neighborList = new Object[v.degree];
		n.weightList = new int[v.degree];
		int i = 0; //counter to keep track of what index we are adding into for the arrays
		
		try {						
			DListNode edgeNode = (DListNode) v.edgeList.front();
			Edge e;
			
			while (edgeNode.isValidNode()) {			
				e = (Edge) edgeNode.item();
				n.neighborList[i] = e.otherVertex(vertex);
				n.weightList[i] = e.weight;		
				edgeNode = (DListNode) edgeNode.next();			
				i++;
			}
		} catch (InvalidNodeException e) {
			Thread.dumpStack();
		}
		return n;
	}

	/**
	 * addEdge() adds an edge (u, v) to the graph.  If either of the parameters
	 * u and v does not represent a vertex of the graph, the graph is unchanged.
	 * The edge is assigned a weight of "weight".  If the edge is already
	 * contained in the graph, the weight is updated to reflect the new value.
	 * Self-edges (where u == v) are allowed.
	 *
	 * NOTE: In my implementation to update the myNode fields of the edge objects,
	 * I depend on the fact that vertex objects' addEdge() method appends it to the 
	 * BACK of the edgeList field of each vertex object.
	 * @param u is a vertex which serves as an endpoint of the graph
	 * @param v is a vertex which serves as the other endpoint of the graph
	 * 
	 * Running time:  O(1).
	 */
	public void addEdge(Object u, Object v, int weight) {
		// Case 1: One of the parameters (or both) do not represent a vertex of the graph.
		Vertex v1,v2;
		v1 = getVertex(u);
		v2 = getVertex(v);
		if (v1 == null || v2 == null) {
			return;
		}
		
		Edge e1,e2;
		VertexPair vpair = new VertexPair(u,v);

		// Case 2: Edge is already in the hashTable. Update weight
		e1 = getEdge(vpair);
		if (e1 != null) {
			e1.weight = weight;
			return;
		}
		
		// Case 3: No edge of (u,v) exists in the graph
		// 0. Create 1 (if u == v) or 2 new edge objects (if u != v)
		// 	  Make sure the the edge objects have their myNode references updated. 
		// 1. Update the corresponding vertex edgeLists (could be 2 or 1 depending 
		//	  if this is a self-edge or not.)
		// 2. Update edgeHash
		// 3. Update edgeTotal
		
		// 0. Creating new Edge objects depending if we have a self edge or not;
		// 1) Adding them to the vertex edgeLists (through addEdge())
		if (u == v) {
			e1 = new Edge(u,v,weight);
			v1.addEdge(e1);
			
			e1.myNode = (DListNode) v1.edgeList.back();
		} else {
			e1 = new Edge(u,v,weight,null);
			e2 = new Edge(u,v,weight,e1);
			e1.partner = e2;

			v1.addEdge(e1);
			v2.addEdge(e2);
			
			e1.myNode = (DListNode) v1.edgeList.back();
			e2.myNode = (DListNode) v2.edgeList.back();
		}
		
		// 2. Updating our edgeHash such that it has the new edge object inside
		// NOTE: we must use e1 because if it is a self-edge, then e1 is the only 
		// edge in consideration (e2 is null) and otherwise if it isn't a self-edge
		// then it doesn't matter whether we use e1 or e2 (we have partner references
		// for each edge object)
		edgeHash.insert(vpair,e1);
		
		// 3. Update edgeTotal
		edgeTotal++;		
	}

	/**
	 * removeEdge() removes an edge (u, v) from the graph.  If either of the
	 * parameters u and v does not represent a vertex of the graph, the graph
	 * is unchanged.  If (u, v) is not an edge of the graph, the graph is
	 * unchanged.
	 * 
	 * NOTE: This method accurately updates the degree's of the vertices associated
	 * with u and v. (the internal representations) It also updates edgeTotal 
	 * properly.
	 * 
	 * @param u is a vertex which serves as an endpoint of the edge (u, v)
	 * @param v is a vertex which serves as another endpoint of the edge (u, v)
	 * 
	 * Running time:  O(1).
	 */
	public void removeEdge(Object u, Object v) {
		Vertex v1,v2;
		v1 = getVertex(u);
		v2 = getVertex(v);
	
		// Case 1: One of the parameters (or both) do not represent a vertex of the graph.
		if (v1 == null || v2 == null) {
			return;
		} 
		
		Edge e = getEdge(new VertexPair(u,v)); 
		// Case 2: the edge is not a vertex on the graph even though u & v are both vertices.
		if (e == null) {
			return;
		}
		// FOR FUTURE: isEdge already looks through to see if there is such an edge in 
		// edgeHash. We can see if Case 1 and case 2 can be combined.
		
		// Case 3: edge exists (e is NOT null), remove it properly.
		// NOTE: when partner is not null, then it is NOT a self edge.(partners must be different!).
		// NEED TO UPDATE:
		// 		v1 degree, v2 degree, edgeTotal, edgeHash.
	
		if (e.partner != null) {
			e.partner.removeMe();
			e.removeMe();
			v1.degree--;
			v2.degree--;
		} else { // is a self edge
			e.removeMe();	
			v1.degree--;
		}
		edgeTotal--;
		
		VertexPair vpair = new VertexPair(u,v);	
		edgeHash.remove(vpair);
		
	}

	/**
	 * isEdge() returns true if (u, v) is an edge of the graph.  Returns false
	 * if (u, v) is not an edge (including the case where either of the
	 * parameters u and v does not represent a vertex of the graph).
	 * @param u is a vertex which serves as an endpoint of the edge (u, v)
	 * @param v is a vertex which serves as another endpoint of the edge (u, v)
	 * @return true if (u, v) is an edge of this graph, false otherwise
	 *
	 * Running time:  O(1).
	 */
	public boolean isEdge(Object u, Object v) {
		Edge e = getEdge(new VertexPair(u,v));
		if (e == null) {
			return false;
		}
		return true;
	}

	/**
	 * weight() returns the weight of (u, v).  Returns zero if (u, v) is not
	 * an edge (including the case where either of the parameters u and v does
	 * not represent a vertex of the graph).
	 *
	 * (NOTE:  A well-behaved application should try to avoid calling this
	 * method for an edge that is not in the graph, and should certainly not
	 * treat the result as if it actually represents an edge with weight zero.
	 * However, some sort of default response is necessary for missing edges,
	 * so we return zero.  An exception would be more appropriate, but
	 * also more annoying.)
	 * 
	 * @param u is a vertex which serves as an endpoint of the edge (u, v)
	 * @param v is a vertex which serves as another endpoint of the edge (u, v)
	 * @return weight of (u, v), or 0 if (u, v) is not an edge
	 *
	 * Running time:  O(1).
	 */
	public int weight(Object u, Object v) {
		// Case 1: Either u or v isn't a vertex of the graph, or edge (u,v) doesn't
		// exist even though u and v exist.
		Edge e = getEdge(new VertexPair(u,v)); 
		if (e == null ) {
			return 0;
		}
		return e.weight; 
	}
	
	
	/********************** HELPER FUNCTIONS ********************************/
	/** 
	 * getVertex() returns the internal vertex object associated with an object.
	 * @param vertex is the application vertex object
	 * @return the internal vertex object or null if no such vertex exists.
	 * 
	 * Running time: O(1)
	 */
	protected Vertex getVertex(Object vertex) {
		Entry vertexEntry = vertexHash.find(vertex);

		// Case 1: No such vertex exists
		if (vertexEntry == null) {
			return null;
		}
		
		// Case 2: return the vertex object
		Vertex v = (Vertex) vertexEntry.value();
		return v;
	}
	
	/**
	 * getEdge() returns an internal representation of edges (an Edge object) from the
	 * edgeHash hash table. 
	 * @param pair is a VertexPair of two objects that is the key for the edgeHash
	 *  hash table.
	 * @return an internal Edge object representation if such an edge is found. Otherwise
	 *  return null.
	 *  
	 *  Running time: O(1)
	 */
	private Edge getEdge(VertexPair pair) {
		Entry edgeEntry = edgeHash.find(pair);

		// Case 1: No such edge exists
		if (edgeEntry == null) {
			return null;
		}
		
		// Case 2: return the vertex object
		Edge e = (Edge) edgeEntry.value();
		return e;
	}
	
	public static void main (String[] args) {

	}
}
